import java.util.*;

public class Solution524 {
    public String findLongestWord(String s, List<String> dictionary) {
        // 将字典按照字典序排序
        for(int i=0;i<dictionary.size()-1;i++){
            for(int j=0;j<dictionary.size()-i-1;j++){
                if(dictionary.get(j+1).compareTo(dictionary.get(j))<0){
                    String temp=dictionary.get(j);
                    dictionary.set(j,dictionary.get(j+1));
                    dictionary.set(j+1,temp);

                }
            }
        }
        System.out.println(dictionary);
        ArrayList<String> res=new ArrayList<>();
        for(int i=0;i<dictionary.size();i++){
            int curChar=0;
            String temp="";
            for(int j=0;j<s.length();j++){
                if(s.charAt(j)==dictionary.get(i).charAt(curChar)){
                    temp+=s.charAt(j);
                    curChar++;
                }
                if(curChar==dictionary.get(i).length()){
                    if(Objects.equals(temp, dictionary.get(i))) {
                        res.add(temp);
                    }
                    break;
                }
            }
            //if(temp==dictionary.get(i)) res.add(temp);
        }
        if(res.size()==0) return "";
        int maxSize=0;
        ArrayList<Integer> max=new ArrayList<>();
        for(int i=0;i<res.size();i++){
            if(res.get(i).length()>maxSize){
                maxSize=res.get(i).length();
            }
        }
        // 找出长度最长的字符串
        for(int i=0;i<res.size();i++){
            if(res.get(i).length()==maxSize){
                max.add(dictionary.indexOf(res.get(i)));
            }
        }
        int[] temp=new int[max.size()];
        for(int i=0;i<max.size();i++){
            temp[i]=max.get(i);
        }
        Arrays.sort(temp);
        String ans=dictionary.get(temp[0]);

        return ans;
    }

    public static void main(String[] args) {
        Solution524 solution524=new Solution524();
        System.out.println(solution524.findLongestWord("abpcplea",
               Arrays.asList(new String[]{"ale", "apple", "monkey", "plea"})));
        System.out.println(solution524.findLongestWord("abce",
                Arrays.asList("abe", "abc")));
        System.out.println(solution524.findLongestWord("apple",
                Arrays.asList("zxc", "vbn")));
    }
}
